//
// Created by zhouheyu on 17-11-30.
//

#include "CFLRU.h"
//创建双向链表
pNode CreateList()
{
    int i,length=0,data=0;
    //分配初始内存
    pNode  pHead=(pNode)malloc(sizeof(Node));
    if(NULL==pHead){
        printf("malloc for pHead failed!\n");
        exit(-1);
    }
    pHead->LPN=-1;
    pHead->isD=-1;
    pHead->Pre=pHead;
    pHead->Next=pHead;

    return pHead;
}

//删除整个链表，释放内存

void FreeList(pNode *ppHead)
{
    pNode pt=NULL;
    while(*ppHead!=NULL){
        pt=(*ppHead)->Next;
        free(*ppHead);
        if(NULL!=pt)
            pt->Pre=NULL;
        *ppHead=pt;
    }
}

//初始化相应的配置参数
void InitVariable()
{
    buf_size=1024*4;
    //设定当前的窗口大小
    alpha=0.4;
    w=(int)(buf_size*alpha+0.5);
    //后续的统计变量
    buffer_cnt=0;
    buffer_hit=0;
    buffer_miss_cnt=0;
    buffer_read_hit=0;
    buffer_read_miss=0;
    buffer_write_hit=0;
    buffer_write_miss=0;
    //物理读写次数
    physical_read=0;
    physical_write=0;
    //设定当前的cflru的长度
    CFLRU_CACHE_SIZE=0;

}


//输出对应的统计结果
void PrintResultStat()
{
    //输出和缓冲区统计相关的信息
    printf("****************************************\n");
    printf("the all buffer req count is %d\n",buffer_cnt);
    printf("the buffer miss count is %d\n",buffer_miss_cnt);
    printf("the hit rate is %f\n",(double)(buffer_cnt-buffer_miss_cnt)/buffer_cnt);
    printf("the buffer read miss count is %d\n",buffer_read_miss);
    printf("the buffer write miss count is %d\n",buffer_write_miss);
    printf("the buffer read hit count is %d\n",buffer_read_hit);
    printf("the buffer write hit count is %d\n",buffer_write_hit);
    printf("the physical read count is %d\n",physical_read);
    printf("the physical write count is %d\n",physical_write);
}


void resetCacheStat()
{
    cache_read_num=0;
    cache_write_num=0;
}

double ComputeCacheDelay()
{
    double delay=0.0;
    double cache_read_delay=0.0;
    double cache_write_delay=0.0;
    cache_read_delay=(double)cache_read_num*(double)CACHE_READ_DELAY;
    cache_write_delay=(double)cache_write_num*(double)CACHE_WRITE_DELAY;
    delay=cache_read_delay+cache_write_delay;
    resetCacheStat();
    return delay;
}

//判断链表是否为空
int IsEmptyList(pNode pHead)
{
    pNode pt=pHead->Next;
    if(pt==pHead)
    {
        return 1;
    }else
    {
        return 0;
    }
}

//返回链表的长度
int GetListLength(pNode pHead)
{
    int length=0;
    pNode pt=pHead->Next;
    while (pt !=pHead)
    {
        length++;
        pt=pt->Next;
    }
    return length;
}

//输出打印链表
void PrintList(pNode pHead)
{
    pNode pt=pHead->Next;
    printf("the list is follow:\n");
    while(pt!=pHead)
    {
        printf("the LPN is %d\t",pt->LPN);
        printf("the isD is %d\n",pt->isD);
        pt=pt->Next;
    }
}

//从链表中插入新的节点,这里之后有读写操作的operation
int InsertEleList(pNode pHead,int pos,int LPN,int operation)
{
    pNode pt=NULL,p_new=NULL;
    pt=pHead->Next;
    if(pos>0&&pos<GetListLength(pHead)+2)
    {
        p_new=(pNode)malloc(sizeof(Node));
        if(NULL==p_new)
        {
            printf("malloc for New Node!\n");
            exit(-1);
        }

        while(1)
        {
            pos--;
            if(0==pos)
                break;
            pt=pt->Next;
        }
        //新建节点
        p_new->LPN=LPN;
        if(operation==0)
            p_new->isD=1;
        else
            p_new->isD=0;
        //这里的双链表是首位相接的，也就是head前面就是最后一个节点
        //插入pt的前面
        p_new->Pre=pt->Pre;
        p_new->Next=pt;
        //衔接
        pt->Pre->Next=p_new;
        pt->Pre=p_new;
        return 1;
    }else {
        return  0;
    }
}

//向链表中删除节点
int DeleteEleList(pNode pHead,int pos)
{
    pNode pt=pHead,ps=NULL;
    //pos=0就是pHead
    if(pos>0&&pos<GetListLength(pHead)+1){
        while(1)
        {
            pos--;
            if(pos==0)
                break;
            pt=pt->Next;
        }
        //此时的pt是pos的前一个节点
        //ps才是要删除的节点位置
        ps=pt->Next;
        pt->Next=ps->Next;
        ps->Next->Pre=pt;
        //释放ps指向的节点
        free(ps);
        return 1;
    }else{
        printf("delete pos %d is error\n",pos);
        return 0;
    }

}

//删除链表的尾部的数据，返回的是删除节点包含的LPN号
int DelLRUList(pNode pHead)
{
    int DelLPN=-1;
    pNode pt=pHead->Pre;
    if(pt==pHead){
        printf("error happend in DelLRUList\n");
        printf("List is empty！！\n");
        exit(-1);
    }
    //将尾部衔接
    pt->Pre->Next=pHead;
    pHead->Pre=pt->Pre;
    //
    DelLPN=pt->LPN;
    if(DelLPN==-1){
        printf("error happend in DelLRUList:\n");
        printf("DelLPN == -1\n");
        exit(-1);
    }
    //释放删除点pt的内存
    free(pt);
    CFLRU_CACHE_SIZE--;
//    错误检测
        if (CFLRU_CACHE_SIZE!=GetListLength(pHead)){
            printf("error happend in DelLRUList:\n");
            printf("CFLRU_CACHE_SIZE is %d\t list-size is %d\t",CFLRU_CACHE_SIZE,GetListLength(pHead));
            exit(-1);
        }

    return DelLPN;
}

//从链表中找到特定的LPN值，并返回节点的指针位置,如果不存在返回NULL
pNode FindLPNinList(pNode pHead,int LPN)
{
    pNode ps=NULL,pt=pHead->Next;
    int count=0;
    while(pt!=pHead)
    {
        count++;
        if(pt->LPN==LPN){
            ps=pt;
            break;
        }
        pt=pt->Next;
    }
    //调试输出语句遍历循环了多少次
//    printf("the while count is %d\n",count);
    return ps;
}

//该函数主要查找队列尾部的优先置换区w中是否存在干净页
//输入参数是优先置换区的大小，输出参数是干净页在队列中的位置，不存在返回NULL
pNode IsCLeanInWindow(pNode pHead,int w)
{
    int index;
    pNode pt, ps=NULL;
    //错误判断
    if(CFLRU_CACHE_SIZE!=buf_size){
        printf("error happend in IsCLeanInWindow:\n");
        printf("CLRU_CACHE_SZIE is %d\t buf_size is %d\n",CFLRU_CACHE_SIZE,buf_size);
        exit(-1);
    }
    //首先指向队列的尾部（LRU）
    pt=pHead->Pre;
    for ( index = 0; index <w ; index++) {
        if (pt->isD==0){
            ps=pt;
            break;
        }
        pt=pt->Pre;
    }

    //    错误检测
    if (CFLRU_CACHE_SIZE!=GetListLength(pHead)){
        printf("error happend IsCLeanInWindow :\n");
        printf("CFLRU_CACHE_SIZE is %d\t list-size is %d\t",CFLRU_CACHE_SIZE,GetListLength(pHead));
        exit(-1);
    }

    return ps;
}

//将命中的数据页移动到MRU位置,输入参数是LRU队列和命中数据页的指针
int MoveTOLRU(pNode pHead,pNode Hit)
{
    pNode pt=NULL,ps=NULL;
    //首先切断原来位置的前后链接关系
    pt=Hit->Pre;
    pt->Next=Hit->Next;
    Hit->Next->Pre=pt;
    //将命中的数据页潜入到头部
    Hit->Pre=pHead;
    Hit->Next=pHead->Next;
    //链接关系
    pHead->Next->Pre=Hit;
    pHead->Next=Hit;
//    //做一个错误检测
//    if(CFLRU_CACHE_SIZE!=GetListLength(pHead)){
//        printf("error happend in MoveToLRU:\n");
//        printf("CFLRU_CACHE_SIZE is %d\t list-size is %d\t",CFLRU_CACHE_SIZE,GetListLength(pHead));
//        exit(-1);
//    }
    return 0;
}

//将miss的请求加入到缓冲区队列,返回的物理读取的时延
double AddNewToBuffer(pNode pHead,int LPN,int operation)
{
    double delay=0.0;
    pNode p_new=NULL;
    p_new=(struct Node*)malloc(sizeof(struct Node));
    if(p_new==NULL){
        printf("error happened in AddNewToBuffer:\n");
        printf("malloc for New node is error\n");
        exit(-1);
    }
    //根据请求初始化对应节点的参数
    if (operation==0){
        buffer_write_miss++;
        cache_write_num++;
        p_new->isD=1;
    } else{
        buffer_read_miss++;
        cache_read_num++;
        p_new->isD=0;
    }
    p_new->LPN=LPN;
    //插入头部
    p_new->Next=pHead->Next;
    p_new->Pre=pHead;
    //链接
    pHead->Next->Pre=p_new;
    pHead->Next=p_new;
    //增加相应的链表长度
    CFLRU_CACHE_SIZE++;
    //调用对应的函数计算延迟
//    delay=callFsim(LPN*4,4,1);
    delay+=FLASH_READ_DELAY;
    physical_read++;
//    错误判读
    if(CFLRU_CACHE_SIZE!=GetListLength(pHead)){
        printf("error happened in AddNewToBuffer:\n");
        printf("CFLRU_CACHE_SIZE is %d\t list-size is %d\t",CFLRU_CACHE_SIZE,GetListLength(pHead));
        exit(-1);
    }
    return delay;
}

//删除是制定的干净页,返回删除的LPN
int DelCleanLPN(pNode pHead,pNode CVictim)
{
    pNode pt=NULL;
    int DelLPN=-1;
    //切断联系
    pt=CVictim->Pre;
    pt->Next=CVictim->Next;
    CVictim->Next->Pre=pt;
    DelLPN=CVictim->LPN;
    //释放对应的节点,释放CVictim节点的内存
    free(CVictim);
    CFLRU_CACHE_SIZE--;
    //错误判读
    if(CFLRU_CACHE_SIZE!=GetListLength(pHead)){
        printf("error happened in DelCleanLPN:\n");
        printf("CFLRU_CACHE_SIZE is %d\t list-size is %d\t",CFLRU_CACHE_SIZE,GetListLength(pHead));
        exit(-1);
    }
    return DelLPN;
}

//缓冲区满的时候将缓冲区中的数据进行移除，返回的是剔除脏页的回写时间
double DelLPNFromBuffer(pNode pHead,int w)
{
    double delay=0.0;
    int DelLPN=-1;
    pNode pC=NULL;
    //首先查看w窗口内是否存在想要的干净页替换
    pC=IsCLeanInWindow(pHead,w);
    if(pC!=NULL){
        //表示存在可以置换的干净页,不需要回写操作
        DelLPN=DelCleanLPN(pHead,pC);
        //错误判断
        if(DelLPN==-1){
            printf("error happend in DelLPNFromBuffer:\n");
            printf("DelClean LPN is -1!!!\n");
            exit(-1);
        }
    }else{
        //表示不存在可以置换的干净页，选择尾部的脏页进行回写
        DelLPN=DelLRUList(pHead);
//        之后调用callFsim函数
        physical_write++;
//        delay+=callFsim(DelLPN*4,4,0);
        delay+=FLASH_WRITE_DELAY;
    }
    return delay;
}


int ZJ_flag=0;
//观测输出的变量
int ObserveCycle=10;
int CycleCount=0;
double DelaySum=0.0;
double AveDelay=0.0;
//last
int Last_buffer_read_miss=0;
int Last_bufer_write_miss=0;
int Last_buffer_cnt=0;
int Last_buffer_miss_cnt=0;
//curr
int Curr_buffer_read_miss;
int Curr_buffer_write_miss;
int Curr_buffer_cnt;
int Curr_buff_miss_cnt;



double CacheManage(int secno,int scount,int operation )
{

    pNode pt = NULL;
    int LPN, LPNCount;
    double cache_delay = 0.0;
    double flash_delay=0.0;
    double delay=0.0;
//    第一次调用的初始化
    if(ZJ_flag==0){
        Head=CreateList();
        InitVariable();
        ZJ_flag=1;
    }
//  页对齐
    LPN = secno / SEC_PRE_PAGE;
    LPNCount = (secno + scount - 1) / SEC_PRE_PAGE - (secno) / SEC_PRE_PAGE + 1;
    resetCacheStat();
//    开始处理请求
    while (LPNCount > 0) {
        buffer_cnt++;
        pt=FindLPNinList(Head,LPN);
        if(pt!=NULL){
            //命中缓冲区
            if(operation==0){
                cache_write_num++;
                buffer_write_hit++;
                pt->isD=1;
            }else{
                cache_read_num++;
                buffer_read_hit++;
            }
            //将命中的数据移动到MRU位置
            MoveTOLRU(Head,pt);
        }else{
            buffer_miss_cnt++;
            //缓冲区满了，需要剔除
            if(CFLRU_CACHE_SIZE>=buf_size){
                flash_delay+=DelLPNFromBuffer(Head,w);
            }
            //将新的请求添加到队列
            flash_delay+=AddNewToBuffer(Head,LPN,operation);
        }
        LPN++;
        LPNCount--;
    }
    cache_delay=ComputeCacheDelay();
    delay=cache_delay+flash_delay;

    //周期观测数据的输出
    if(0 == CycleCount % ObserveCycle && CycleCount != 0){
        AveDelay=DelaySum/ObserveCycle;
        DelaySum=0.0;
        printf("the %d Request,the AveDelay is %f\n",CycleCount,AveDelay);
        Curr_buff_miss_cnt=buffer_miss_cnt-Last_buffer_miss_cnt;
        Curr_buffer_cnt=buffer_cnt-Last_buffer_cnt;
        Curr_buffer_read_miss=buffer_read_miss-Last_buffer_read_miss;
        Curr_buffer_write_miss=buffer_write_miss-Last_bufer_write_miss;
        printf("the Curr_buff_cnt is %d\tbuffer miss cnt is %d\n",Curr_buffer_cnt,Curr_buff_miss_cnt);
        printf("the Curr buff read miss is %d\t write miss is %d\n",Curr_buffer_read_miss,Curr_buffer_write_miss);
        Last_buffer_cnt=buffer_cnt;
        Last_buffer_miss_cnt=buffer_miss_cnt;
        Last_buffer_read_miss=buffer_read_miss;
        Last_bufer_write_miss=buffer_write_miss;
        printf("..............................................................\n");
        CycleCount++;
    }else{
        DelaySum+=delay;
        CycleCount++;
    }




    return delay;
}
